/*
 * @Author: szx
 * @Date: 2021-11-02 13:00:00
 * @LastEditTime: 2021-11-02 13:18:56
 * @Description:
 * @FilePath: \leetcode\100-199\141\141.cpp
 */
#include <iostream>
#include <unordered_set>
using namespace std;
struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(NULL) {}
};

// class Solution {
//    public:
//     bool hasCycle(ListNode* head) {
//         ListNode* ptr = head;
//         unordered_set<ListNode*> set;
//         while (ptr != nullptr) {
//             auto it = set.find(ptr);
//             if (it != set.end()) {
//                 return true;
//             }
//             set.insert(ptr);
//             ptr = ptr->next;
//         }
//         return false;
//     }
// };

// class Solution {
//    public:
//     bool hasCycle(ListNode* head) {
//         ListNode* ptr = head;

//         while (ptr != nullptr) {
//             if (ptr->val == 1000000) {
//                 return true;
//             }
//             ptr->val = 1000000;
//             ptr = ptr->next;
//         }
//         return false;
//     }
// };


class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};


int main() { return 0; }